from FileProcess import *

INF = float('inf')


class Algorithm:
    """this class is the implement and improvement of graph search algorithm"""

    lines = {}
    subwayMap = {}  # record the current city map
    _stationsDistance = []  # for dijkstra algorithm
    locationDic = {}  # record the corresponding index of a certain location
    graph = []  # the adjacency list form of the graph. Being used in dijkstra algorithm
    # 后三个属性都要在建模的时候补充

    _fileAddress = "D:/desktop/history.txt"
    file = FileProcess(_fileAddress)

    # @staticmethod
    # def _graphInitialize(func):
    #
    #     def mainFunction():
    #
    #     mainFunction()
    #     func()
    #     return mainFunction

    @staticmethod
    def dijkstra(origin: int, destination: int):
        """
        the main content of the dijkstra algorithm.
        The form of the graph should follow the pattern in PPT.
        :param origin:      the starting station
        :param destination: the ending station
        :return:            a list containing the stations the shortest route passed by
        """

        path = []
        searchedVertexes = [0] * Algorithm.graph.n
        # unSearchedVertexes = [0] * Algorithm.graph.n

        for dis in Algorithm.graph.edges[origin]:
            # initialize the distance sequence
            Algorithm._stationsDistance.append(dis)
            # initialize the path list
            if dis < INF:
                path.append(origin)
            else:
                path.append(-1)

        # main function
        while Algorithm._stationsDistance[destination] == -1:
            minDis = INF
            newVex = -1
            for j in range(Algorithm.graph.n):
                if searchedVertexes[j] == 0 and Algorithm._stationsDistance[j] < minDis:
                    minDis = Algorithm._stationsDistance[j]
                    newVex = j
            searchedVertexes[newVex] = 1
            for j in range(Algorithm.graph.n):
                if searchedVertexes[j] == 0:
                    if Algorithm.graph.edges[newVex][j] < INF and Algorithm._stationsDistance[newVex] + \
                            Algorithm.graph.edges[newVex][j] < \
                            Algorithm._stationsDistance[j]:
                        Algorithm._stationsDistance[j] = Algorithm._stationsDistance[newVex] + \
                                                         Algorithm.graph.edges[newVex][j]
                        path[j] = newVex

        route = []
        temp = destination
        while route[-1] != origin:
            route.append(temp)
            temp = path[destination]
        route.reverse()
        return route, path[destination]

    @staticmethod
    def minDistanceSearch(start, goal):
        """
        BFS implement in this specific model
        :param start: the departure station
        :param goal: the destination
        :return:
        """
        if not Algorithm.subwayMap:
            raise Exception("Map hasn't initialized")
        if start == goal:
            return [start]
        explored = set()
        explored.add(start)
        # three elements in the tuple correspond to "current line", "change time" and "travel distance"
        queue = [[start, ('', -1, 0)]]

        def temp(elem):
            return elem[-1][-1]

        while queue:
            path = queue.pop(0)
            station = path[-2]
            lineNum, changeTimes, currentDistance = path[-1]
            initialIndex = 1
            if station == goal:
                return path
            try:
                for state, action in Algorithm.subwayMap[station].items():
                    if "distance" not in state:
                        if state not in explored:
                            lineChange = changeTimes
                            newDistance = currentDistance + int(
                                Algorithm.subwayMap[station]["distance" + str(initialIndex)])
                            explored.add(state)
                            if lineNum != action:
                                lineChange += 1
                            path2 = path[:-1] + [action, state, (action, lineChange, newDistance)]
                            queue.append(path2)
                        initialIndex += 1
                queue.sort(key=temp)
            except KeyError:
                print("无效输入")
                return []
        return []

    @staticmethod
    def minChangeSearch(start, goal):
        """
        BFS implement in this specific model
        :param start: the departure station
        :param goal: the destination
        :return:
        """
        if not Algorithm.subwayMap:
            raise Exception("Map hasn't initialized")
        if start == goal:
            return [start]
        explored = set()
        explored.add(start)
        # three elements in the tuple correspond to "current line", "change time" and "travel distance"
        queue = [[start, ('', -1, 0)]]
        while queue:
            path = queue.pop(0)
            station = path[-2]
            lineNum, changeTimes, currentDistance = path[-1]
            initialIndex = 1
            if station == goal:
                return path
            try:
                for state, action in Algorithm.subwayMap[station].items():
                    if "distance" not in state:
                        if state not in explored:
                            lineChange = changeTimes
                            newDistance = currentDistance + int(
                                Algorithm.subwayMap[station]["distance" + str(initialIndex)])
                            explored.add(state)
                            if lineNum != action:
                                lineChange += 1
                            path2 = path[:-1] + [action, state, (action, lineChange, newDistance)]
                            queue.append(path2)
                        initialIndex += 1
                queue.sort(key=lambda changeCount: path[-1][-2])
            except KeyError:
                print("无效输入")
                return []
        return []

    @staticmethod
    # @_graphInitialize  # 这里记得写完之后去掉注释
    def mapInitialize(**lines):
        """
        Input is build_subway(linename='station1 station2...'...)
        Ouput is a dictionary like {station:{neighbor1:line number,neighbor2:line number,...},station2:{...},...}
        """
        Algorithm.lines = lines
        for key in lines.keys():
            value = lines[key]
            lines[key] = value.split()
        stations = set()
        for key in lines.keys():
            stations.update(set(lines[key]))
        system = {}
        for station in stations:
            next_station = {}
            distanceCount = 1
            for key in lines:
                if station in lines[key]:
                    line = lines[key]
                    idx = line.index(station)
                    if idx == 0:
                        next_station[line[idx + 2]] = key
                        next_station["distance" + str(distanceCount)] = line[idx + 1]
                        distanceCount += 1
                    elif idx == len(line) - 1:
                        next_station[line[idx - 2]] = key
                        next_station["distance" + str(distanceCount)] = line[idx - 1]
                        distanceCount += 1
                    else:
                        next_station[line[idx - 2]] = key
                        next_station["distance" + str(distanceCount)] = line[idx - 1]
                        distanceCount += 1
                        next_station[line[idx + 2]] = key
                        next_station["distance" + str(distanceCount)] = line[idx + 1]
                        distanceCount += 1
            system[station] = next_station

        Algorithm.subwayMap = system
        return

    @staticmethod
    def recommendRoute(date=time.strftime("%Y-%m-%d", time.localtime())):
        for i in Algorithm.file.text:
            if date in i:
                temp = i.split()
                return temp[0], temp[1]


if __name__ == '__main__':
    Algorithm.mapInitialize(line1=u'''西塱 1 坑口 1 花地湾 1 方寸 1 黄沙 1 长寿路 1 陈家祠 1 西门口 1 公元前 1 农讲所 1 烈士陵园 1 东山口 1 杨箕 1 
    体育西路 1 体育中心 1 广州东站''',
                            line2=u'''广州南站 1 石壁 1 会江 1 南浦 1 洛溪 1 南洲 1 东晓南 1 江泰路 1 昌岗 1 江南西 1 市二宫 1 海珠广场 1 公元前 1 纪念堂 
                            1 越秀公园 3 广州火车站 1 三元里 1 飞翔公园 1 白云公园 1 白云文化广场 1 萧岗 1 江夏 1 黄边 1 嘉禾望岗 ''',
                            line3=u'''机场北 1 机场南 1 高增 1 人和 1 龙归 1 嘉禾望岗 1 白云大道北 1 永泰 1 同和 1 京溪南方医院 1 梅花园 1 燕塘 1 广州东站 
                            1 林和西 1 体育西路 1 珠江新城 1 广州塔 1 客村 1 大塘 1 沥滘 1 大石 1 汉溪长隆 1 市桥 1 番禺广场 ''',
                            line5=u'''窖口 1 坦尾 1 中山八 1 西场 1 西村 1 广州火车站 1 小北 1 淘金 1 区庄 1 动物园 1 杨箕 1 五羊邨 1 珠江新城 1 猎德 1 
                            潭村 1 员村 1 科韵路 1 车陂南 1 东圃 1 三溪 1 鱼珠 1 大沙地 1 大沙东 1 文冲 ''',
                            line6=u'''河沙 1 坦尾 1 如意坊 1 黄沙 1 文化公园 1 一德路 1 海珠广场 1 北京路 1 团一大广场 1 东湖 1 东山口 1 区庄 1 黄花岗 1 
                            沙河顶 1 天平架 1 燕塘 1 天河客运站 1 植物园''',
                            line7=u'''广州南站 1 石壁 1 谢村 1 钟村 1 汉溪长隆 1 南村万博 1 员岗 1 板桥 1 大学城南''',
                            line8=u'''万胜围 1 琶洲 1 新港东 1 磨碟沙 1 赤岗 1 客村 1 鹭江 1 中大 1 晓港 1 昌岗 1 宝岗大道 1 沙园 1 凤凰新村 1 同福西 1 
                            文化广场 1 华林寺 1 陈家祠 1 彩虹桥 1 西村 1 鹅掌坦 1 同德''')

    # 输入测试
    print(Algorithm.minChangeSearch("三元里", "三元里"))
    print(Algorithm.minChangeSearch("万胜围", "西塱"))
    print(Algorithm.minDistanceSearch("三元里", "烈士陵园"))
    print(Algorithm.minDistanceSearch("烈士陵园", "三元里"))
    print(Algorithm.minDistanceSearch("a", "b"))
